#include"Sort.h"

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n-gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

int GetMidi(int* a, int left,int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//left<mid
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSortHoare(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <=a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);
	return left;
}

int PartSortHole(int* a, int left, int right)
{
	int hole = left;
	int key = a[left];
	while (left < right)
	{
		while (left<right && a[right]>=key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return left;
}

int PartSortPoint(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && prev++ != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;

}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((end - begin) >= 10)
	{
		int ret = PartSortHoare(a, begin, end);
		//int ret = PartSortHole(a, begin, end);
		//int ret = PartSortPoint(a, begin, end);
		QuickSort(a, begin, ret - 1);
		QuickSort(a, ret + 1, end);
	}
	else
	{
		InsertSort(a+begin, end-begin+1);
	}
}

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STinit(&st);
	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);

		int right = STTop(&st);
		STPop(&st);

		int key = PartSortHoare(a, left, right);
		if (key + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		if (key - 1 > left)
		{
			STPush(&st, key - 1);
			STPush(&st, left);
		}
	}
	STDestory(&st);
}

void _MargeSort(int* a, int* tmp, int left, int right)
{
	if (left >= right)
	{
		return;
	}  
	int mid = (left + right) / 2;
	_MargeSort(a, tmp, left, mid);
	_MargeSort(a, tmp, mid+1, right);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	memcpy(a + left, tmp + left, (end2 - left + 1) * sizeof(int));

	
}

void MargeSort(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	_MargeSort(a, tmp, 0, n - 1);

	free(tmp);
}

void MergeSortSNonR(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i+=gap*2)
		{
			int begin1 = i, end1 = begin1 + gap-1;
			int begin2 =end1+1, end2 = begin2 + gap-1;
			int index = i;
			if (begin2 >= n)
			{
				break;
			}
			if (end2 > n-1)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (end2 - i+1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max=a[i];
		}
		if (a[i] < min)
		{
			min= a[i];
		}
	}
	int range = max-min+1;
	int* Count = (int*)calloc(range, sizeof(int));
	for (int i = 0; i < n; i++)
	{
		Count[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (Count[i]--)
		{
			a[j++] = i + min;
		}
	}
}
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	for (int i = (n - 2) / 2; i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		end--;
	}
}


//void Swap(int* a, int* b)
//{
//	int tmp = *a;
//	*a = *b;
//	*b = tmp;
//}
int getMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else {
			return right;
		}
	}
}
